package com.exam.demo;

import org.junit.Test;
import org.springframework.boot.test.context.SpringBootTest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

@SpringBootTest
public class EightQueens {
    //maxSize表示皇后数量
    static int maxSize = 8;
    //array表示摆放位置(把二维数组压缩为一维数组，二维数组的第i+1行第j+1列在一维数组中用array[i]=j表示)
    //array[i]=j--i表示第i+1行的皇后
    //array[i]=j--j表示第j+1列的皇后
    static int[] array = new int[maxSize];
    //count表示共有多少种解法
    static int count = 0;

    public static void main(String[] args) {
        EightQueens queue = new EightQueens();
        queue.put(0);
        System.out.println("共有" + count + "种解法");
    }

    //放置第n个皇后
    public void put(int n) {
        if (n == maxSize) { //前8个皇后已经摆放好，直接输出结果
            count++;
            printQueens();
            return;
        } else {
            for (int i = 0; i < maxSize; i++) {
                array[n] = i;
                if (judge(n)) { //如果所放的位置与其他皇后不冲突，则直接放置下一个皇后
                    put(n + 1);
                } else { //如果冲突，则放到第i+1列并再次判断
                    continue;
                }
            }
        }
    }

    //判断放置第n个皇后，位置是否与其他皇后冲突
    public boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[i] - array[n])) { //表示第n个皇后摆放的位置的那一列与第i个皇后冲突||第n个皇后的斜线上与第i个皇后冲突
                return false;
            }
        }
        return true;
    }


    private static void printQueens() {
        for (int row = 0; row < maxSize; row++) {
            for (int col = 0; col < maxSize; col++) {
                if (array[row] == col) {
                    System.out.print("Q ");
                } else {
                    System.out.print("- ");
                }
            }
            System.out.println();
        }
        System.out.println("当前求解数量：" + count);
        System.out.println("====================");
    }

}
